package org.example.hashAndSet;

public class Code04_FindFirstIntersectNode {
    public static class Node {
        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }

    //判断链表是否有环  没有就返回空 有就返回环的第一个节点
    public static Node getLoopNode(Node head) {
        if (head == null || head.next == null || head.next.next ==null) {
            return null;
        }
        Node n1 = head.next;  // n1   S 、慢指针
        Node n2 = head.next.next;  // n2   F   快指针
        while(n1 != n2) {
            if(n2.next == null || n2.next.next == null) {
                return null;
            }
            n2 = n2.next.next;
            n1 = n1.next;
        }
        //上面走完 n1 = n2
        //找环的第一个节点  n2回到 head n1 n2个走一步 相遇即为第一个节点
        n2 = head;
        while (n1 != n2) {
            n1 = n1.next;
            n2 = n2.next;
        }
        return n1;
    }

    //如果两个链表都无环，则返回第一个相交节点，如果不相交 null
    public static Node noLoop(Node head1,Node head2) {
        if(head1 == null || head2 == null) {
            return null;
        }
        Node cur1 = head1;
        Node cur2 = head2;
        int n = 0;
        while (cur1.next != null) {
            cur1 = cur1.next;
            n++;
        }
        while (cur2.next != null) {
            cur2 = cur2.next;
            n--;
        }
        if(cur1 != cur2) {
            return  null;
        }
        cur1 = n > 0 ? head1:head2;
        cur2 = cur1 == head1 ? head2:head1;
        n = Math.abs(n);
        while (n != 0) {
            cur1 = cur1.next;
            n--;
        }
        while (cur1 != cur2) {
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }

    //两个有环链表，返回第一个相交节点，不相交 null
    public static Node bothLoop(Node head1,Node loop1,Node head2,Node loop2) {
        Node cur1 = null;
        Node cur2 = null;
        if(loop1 == loop2) {
            cur1 = loop1;
            cur2 = loop2;
            int n = 0;
            while (cur2 != loop2) {
                n--;
                cur2 = cur2.next;
            }
            while (cur1 != loop1) {
                n++;
                cur1 = cur1.next;
            }
            cur1 = n > 0 ? head1:head2;
            cur2 = cur1 == head1 ? head2:head1;
            n = Math.abs(n);
            while (n != 0) {
                cur1 = cur1.next;
                n--;
            }
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        }else {

            cur1 = loop1.next;
            while (cur1 != loop1) {
                if (cur1  == loop2) {
                    return loop1;
                }
                cur1 = cur1.next;
            }
            return null;
        }
    }
}
